LeetCode 300. Longest Increasing Subsequence 最长上升子序列

Posted on | In

300. Longest Increasing Subsequence

题目描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

示例:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

解答

这道题是典型的dp问题，我们先创建一个dp数组，其中dp[i]表示到i为止最长上升子序列,则dp[i]=max(dp[j])+1 0 <= j < i。

遍历i从1到n-1，j从0到i - 1即可得到dp数组，dp数组中最大的值就为解（解法1）。

另一种思路是，我们也先创建一个dp数组，这个数组保存目前最长的最长上升子序列。

当遍历数组nums的时候，我们尝试向这个dp数组中用二分法查找并插入当前元素（每次插入都保证这个数组是排好序的）。

当dp数组中最大值小于nums[i], 我们就像dp数组尾部加入nums[i]。否则就令dp数组中刚好大于nums[i]的这个值用nums[i]替换掉，最后dp数组的长度就是最长上升子序列（解法2）。

在解法2中，若插入在dp数组的尾部，最长上升子序列的长度加1，若替换掉dp数组中的某个值，不改变已有的最长上升子序列的长度，所以解法2是正确的。

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> vec(n, 1);
        Max = 0;
        for (int i = 1; i < nums.size(); i++) {
        	for (int j = 0; j < i; j ++) {
        		if (nums[i] > nums[j]) {
        			vec[i] = max(vec[i], vec[j] + 1);
        			Max = max(Max, vec[i]);
        		}
        	}
        }
        return Max;
    }
};

解法2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
	    vector<int> res;
	    for(int i=0; i<nums.size(); i++) {
	        auto it = lower_bound(res.begin(), res.end(), nums[i]);
	        if(it==res.end()) res.push_back(nums[i]);
	        else *it = nums[i];
	    }
	    return res.size();
	}
};